package chapter03_binaryTree;

import java.util.HashMap;

/**
 * 描述：
 *      符合搜索二叉树的最大拓扑结构
 * @author hl
 * @date 2021/5/10 9:45
 */
public class MaxTopo {
    public static void main(String[] args) {
        SerialBinaryTree serialBinaryTree = new SerialBinaryTree();
        Node head = serialBinaryTree.reconByLevel("6!1!12!0!3!10!13!#!#!#!#!4!14!20!16!2!5!11!15!#!#!#!#!#!#!#!#!#!#!#!#!");
//        new PrintTree().printTree(head);
        MaxTopo maxTopo = new MaxTopo();
        int size = maxTopo.bstTopoSize2(head);
        System.out.println(size);
    }

    /**
     * 方法一：时间复杂度为O(n^2)
     * 先考查h的孩子结点，然后根据孩子结点的值按照二叉搜索的方式进行移动，如果最后能移动到同一个孩子身上，那么说明
     * 这个孩子可以作为这个拓扑结构的一部分。
     * @param head
     * @return
     */
    public int bstTopoSize(Node head){
        if (head == null) {
            return 0;
        }
        int max = maxTopo(head, head);
        max = Math.max(bstTopoSize(head.left), max);
        max = Math.max(bstTopoSize(head.right), max);
        return max;
    }

    private int maxTopo(Node h, Node n) {
        if (h != null && n != null && isBSTNode(h, n, n.val)) {
            return maxTopo(h, n.left) + maxTopo(h, n.right) + 1;
        }
        return 0;
    }

    private boolean isBSTNode(Node h, Node n, int val) {
        if (h == null) {
            return false;
        }
        if (h == n) {
            return true;
        }
        return isBSTNode(h.val > val ? h.left : h.right, n, val);
    }

    /**
     * 方法二：最好情况下时间复杂度为O(n),最差情况下时间复杂度为O(nlogn)的
     * 在遍历过程中，自下而上，为每个结点生成以该结点h为头的拓扑贡献记录
     * （l,r）l表示以h为头结点的左子树可以为当前头结点拓扑结构贡献的贡献几个结点；
     *  r表示以r为头结点的右子树可以为当前结点的拓扑结构贡献几个结点；
     *  在后序遍历的过程中，自下而上的为每个结点生成并更新之前结点的拓扑贡献记录，从而通过比较返回最大的拓扑结构的结点个数
     *
     *  最好的情况是二叉树是棒状结构，最差的情况是二叉树为满二叉树
     * @param head
     * @return
     */
    public int bstTopoSize2(Node head){
        HashMap<Node, Record> map = new HashMap<>();
        return posOrder(head, map);
    }

    private int posOrder(Node h, HashMap<Node, Record> map) {
        if (h == null) {
            return 0;
        }
        int ls = posOrder(h.left, map);
        int rs = posOrder(h.right, map);
        modifyMap(h.left, h.val, map, true);
        modifyMap(h.right, h.val, map, false);
        Record lr = map.get(h.left);
        Record rr = map.get(h.right);
        int lbst = lr == null ? 0 : lr.l + lr.r + 1;
        int rbst = rr == null ? 0 : rr.l + rr.r + 1;
        map.put(h, new Record(lbst, rbst));
        return Math.max(lbst + rbst + 1, Math.max(ls, rs));
    }

    /**
     * 修改以val值为头结点的左右子树的结点贡献记录的值
     * @param h
     * @param val
     * @param map
     * @param s 为true代表当前结点为左孩子，false代表当前结点为右孩子
     * @return
     */
    private int modifyMap(Node h, int val, HashMap<Node, Record> map, boolean s) {
        if (h == null || !map.containsKey(h)) {
            return 0;
        }
        Record r = map.get(h);
        if ((s && h.val > val) || (!s && h.val < val)) {
            map.remove(h);
            return r.l + r.r + 1;
        }else{
            int minus = modifyMap(s ? h.right : h.left, val, map, s);
            if (s) {
                r.r = r.r - minus;
            }else{
                r.l = r.l - minus;
            }
            //修改结点的贡献记录
            map.put(h, r);
            return minus;
        }
    }

    class Record{
        int l;
        int r;

        public Record(int l, int r) {
            this.l = l;
            this.r = r;
        }
    }


}
